21. Merge Two Sorted Lists

问题

Merge two sorted linked lists and return it as a new list.

思路

这个题目很简单也有几个可以考虑的思路，一个是比较直接的方式，重新构造链表，一种是利用递归

思路1 ：用新的链表

这里用了一个新的节点了保存结果的链表，这里为了方便链表的扩充，增加一个临时的节点变量（否则每次加入都要遍历到尾部）

  1. public class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         ListNode result = new ListNode(0);
  4.         ListNode tmp = result;
  5.         while(l1 != null || l2 != null)
  6.         {
  7.             if(l2 == null || (l1 != null && l1.val <= l2.val))
  8.             {
  9.                 tmp.next = l1;
  10.                 l1 = l1.next;
  11.             }
  12.             else 
  13.             {
  14.                 tmp.next = l2;
  15.                 l2 = l2.next;
  16.             }
  17.             tmp = tmp.next;
  18.         }
  19.         return result.next;
  20.     }
  21. }

思路2：递归方案

在很多时候，递归的方案可以提供一种清晰简单的解决方案，代码也更精炼。但是递归有个问题就是容易出现堆栈溢出的问题。

  1. public:
  2.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  3.         if(l1 == NULL) return l2;
  4.         if(l2 == NULL) return l1;
  6.         if(l1->val < l2->val) {
  7.             l1->next = mergeTwoLists(l1->next, l2);
  8.             return l1;
  9.         } else {
  10.             l2->next = mergeTwoLists(l2->next, l1);
  11.             return l2;
  12.         }
  13.     }
  14. };